/*
 * @lc app=leetcode.cn id=148 lang=cpp
 *
 * [148] 排序链表
 *
 * https://leetcode-cn.com/problems/sort-list/description/
 *
 * algorithms
 * Medium (66.52%)
 * Likes:    1528
 * Dislikes: 0
 * Total Accepted:    267.8K
 * Total Submissions: 402.6K
 * Testcase Example:  '[4,2,1,3]'
 *
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 *
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 *
 *
 * 示例 2：
 *
 *
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 *
 *
 * 示例 3：
 *
 *
 * 输入：head = []
 * 输出：[]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 链表中节点的数目在范围 [0, 5 * 10^4] 内
 * -10^5 <= Node.val <= 10^5
 *
 *
 *
 *
 * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//   Definition for singly-linked list.
/* struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
}; */

class Solution
{

public:
    static bool issmaller(ListNode *p1, ListNode *p2)
    {
        if (p1->val < p2->val)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    ListNode *sortList(ListNode *head)
    {
        if (!head || !head->next)
        {
            return head;
        }
        vector<ListNode *> vec;
        ListNode *ptr = head;
        while (ptr)
        {
            vec.push_back(ptr);
            ptr = ptr->next;
        }
        sort(vec.begin(), vec.end(), issmaller);
        ListNode *newhead;
        newhead = vec[0];
        ptr = newhead;
        for(int i=1;i<vec.size();i++){
            ptr->next=vec[i];
            ptr=vec[i];
        }
        ptr->next=nullptr;
        return newhead;
    }
};
// @lc code=end
